package Algorithm.BitOperation;

/**
 * 461. 汉明距离 https://leetcode.cn/problems/hamming-distance
 * 题目简述：两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。计算返回整数x和y的汉明距离
 */
public class HammingDistance {

    public static void main(String[] args) {
        byte a = 3; //二进制补码：0000 0011
        byte b = -2;//二进制补码：1111 1110
        System.out.print(a & b); //打印结果：2
    }

    /**
     * 思路一：逐位比较
     * 通过(x >> i) & 1运算来遍历x的32位补码
     */
    public int hammingDistance(int x, int y) {
        int count = 0;
        for (int i = 0;i < 32;i++) {
            //先右移i位然后再与00000000 00000000 00000000 00000001按位与，即可得32位补码中第i+1位的码值
            int a = (x >> i) & 1;
            int b = (y >> i) & 1;
            //然后再进行异或运算，判断二进制位是否相同
            count += a^b;
        }
        return count;
    }

    /**
     * 思路二：右移统计
     * 每次都统计当前 x 和 y 的最后一位，统计完则将 x 和 y 右移一位。
     * 当 x 和 y 的最高一位 1 都被统计过之后，循环结束。
     */
    public int hammingDistance2(int x, int y) {
        int count = 0;
        while ((x | y) != 0) {
            int a = x & 1;
            int b = y & 1;
            count += a ^ b;
            x >>= 1;
            y >>= 1;
        }
        return count;
    }

    /**
     * 思路三：异或后再统计结果中1的数量
     */
    public int hammingDistance3(int x, int y) {
        int count = 0;
        int t = x ^ y;
        while (t != 0) {
            count += t & 1;
            t >>>= 1;//无符号右移后再赋值。带符号右移对于负数高位会补1，陷入死循环
        }
        return count;
    }

    /**
     * 思路四：异或后再统计结果中1的数量。题设已说明x,y都是非负数，故异或结果也是非负，故可通过每次用lowbit函数获取t最低位1数值 然后t再减去这个值，直到t为0，则t中所有1都已减去
     */
    public int hammingDistance4(int x, int y) {
        int count = 0;
        for (int t = x ^ y;t != 0;t -= lowbit(t))
            count++;
        return count;
    }

    /**
     * lowbit函数：获取二进制数中最低位的1所对应的数值
     * 负数的补码等于其原码最低位1左边所有数值位按位取反，故 t & -t就等于t的最低位1所对应的数值
     * 例：t = 0011 0100 则-t = 1100 1100 故 0011 0100 & 1100 1100 = 0000 0100
     */
    public int lowbit(int t) {
        return t & -t;
    }
}
